Анотація: В даній курсовій роботі реалізується програма, яка стискає текстову інформацію з деякого вхідного файлу, і записує її у новий файл , при цьому займаючи менше місця на диску. Крім того, дана програма розпаковує стиснений нею файл і записує отриману інформацію у вихідний файл. Стиск інформації проводився згідно алгоритму Лемпеля-Зіва-Велча. На прикладі даної програми мною вивчалася можливість створення компресора - завдання, реалізація якого є достатньо потрібною на сучасному етапі розвитку інформаційних технологій. ЗМІСТ Вступ…………………………………………………………………………...3 Методи стиску………………………………………………………………...4 Стиснення інформації способом кодування серій (RLE)…………..….4 Арифметичне кодування………………………………………………....4 Алгоритм Лемпеля-Зіва-Велча (Lempel-Ziv-Welch - LZW)………….....5 Стиснення даних кодом Хафмана……………………………………....5 Принцип роботи алогритму Лемпеля-Зіва-Велча……………………...….6 2.1Варіанти удосконалення………………………………………………….8 Опис програми………………………………………………………………..9 Опис процедур програми ……………………………………….…………...9 4.1 Процедура стиску.…………………………….………………………...10 4.2 Процедура хешування....……………………….………………………...11 4.3 Процедура розпакування..…………………….………………………....12 4.4.Процедура декодування…………….……………………….…………...14 4.5.Процедура вводу коду змінної довжини………………………….…….15 4.6.Процедура виводу коду змінної довжини…….………………………...15 Висновок………………………………………………………………………16 Список літератури……………………………………………………………17 Додаток А…………………………………………………………………......18 Додаток В……………………………………………………………………..24 Вступ Характерною особливістю більшості типів даних є їх надлишковість. Для людини надлишковість даних часто пов'язана з якістю інформації, оскільки надлишковість, як правило, покращує зрозумілість та сприйняття інформації. Однак, коли мова йде про зберігання та передачу інформації засобами комп'ютерної техніки, то надлишковість відіграє негативну роль, оскільки вона приводить до зростання вартості зберігання та передачі інформації. Особливо актуальною є ця проблема у випадку необхідності обробки величезних обсягів інформації при незначних об'ємах носіїв даних. У зв'язку з цим постійно виникає проблема позбавлення надлишковості або стиснення даних. Основний принцип, на якому базується стиснення даних, полягає в економічному описі повідомлення, згідно якому можливе відновлення початкового його значення з похибкою, яка контролюється. Існує багато методів стиску інформації, кожен з яких має свої особливості, але ми розглянемо алгоритм Лемпеля-Зіва-Велча, у якому є таблиця перетворення рядків, так званий словник. Цей алгоритм будує словник саме під час опрацювання тексту, що дозволяє йому бути універсальним алгоритмом і не приносити додаткових затрат на збереження єдиного великого словника для всіх стиснутих файлів. 1.Методи стиску 1.1Стиснення інформації способом кодування серій (RLE): Найбільш відомий, простий підхід і алгоритм стиснення інформації оборотним шляхом - це кодування серій послідовностей (Run Length Encoding - RLE). Суть методів даного підходу полягає в заміні ланцюжків або серій байтів що повторюються або їх послідовностей на один лічильник, що кодує байт і числа їх повторень. Приклад: 44 44 44 11 11 11 11 11 01 33 FF 22 22 - вихідна послідовність 03 44 04 11 00 03 01 03 FF 02 22 – послідовність після стиснення. Перший байт вказує скільки раз потрібно повторити наступний байт. Якщо перший байт рівний 0, то потім пишеться лічильник, що показує скільки за ним йде неповторюваних даних. Даний метод, як правило, досить ефективний для стиснення графічних зображень. Недоліком методу RLE є досить низька ступінь стиснення. 1.2Арифметичне кодування: Арифметичне кодування є методом, що дозволяє стиснути символи вхідного алфавіту без втрат за умови, що відомий розподіл частот цих символів і є найбільш оптимальним, тому що досягається теоретична межа ступені стиснення. Передбачувана необхідна послідовність символів, при стисненні методом арифметичного кодування розглядається як деякий двійковий дріб з інтервалу ...